+from Crypto.Util.number import *
from gmpy2 import *
import os

flag = b'xxx'
def Mypow(b, e, mod):
    a = 1
    while e:
        e >>= 1
        b = (b*b)%mod
        if e&1:
            a = (a*b)%mod
    return a

def Genp(bit_length):
    coeff = 2 ** 5 * 3 * 7
    while True:
        tmp_prime = getRandomNBitInteger(bit_length - 10)
        p = coeff * tmp_prime + 1
        if is_prime(p):
            break
    return p

def Genkeys(bit_length):
    p,q = Genp(bit_length),Genp(bit_length)
    n = p * q
    hint = (2 * p + 7 * q) % n
    return n, hint

if __name__ == '__main__':
    e = next_prime(666)
    n, hint = Genkeys(512)
    m = bytes_to_long(os.urandom(30) + flag)
    ct = Mypow(m,e,n)
    print(f'n = {n}')
    print(f'hint = {hint}')
    print(f'ct = {ct}')

    '''
    n = 36443283250594259606482132779262570582448178589602577809591307671554949253094255209079689901493052116793388954529442162972106210862341856282788030374324677114528044629385805693771773377070021111949953333360526159026822968061585876873187059674130307295006486032106471182393880915860569773206853864515489855553
    hint = 57792516722001523643789088224096258172899052039145876393373730235406451592173971020702024058282699663364267742428240581839287357212741266617791207580236457
    ct = 24482128269957355675512496312977308128712253968496848873519792376434347925427116612997489113223781321628516365811583310346553402215907938918891908853234881284620764982626375301219763593402089309909155204943747718536894186749932544428588048770663458669109073657836937287831725958017345747881678942488157429000
    '''
